package array.binarySearch;

/**
 * 给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。
 * 换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。
 * 注意：0 既不是正整数也不是负整数。
 * 示例 1：
 * 输入：nums = [-2,-1,-1,1,2,3]
 * 输出：3
 * 解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3
 */
class MaximumCount {
    public int maximumCount(int[] nums) {
        int n = nums.length;

        // 1. 查找第一个非负数位置 (>=0)
        int firstNonNegative = findFirstNonNegative(nums);
        int negCount = firstNonNegative; // 负数个数

        // 2. 查找第一个正数位置 (>0)
        int firstPositive = findFirstPositive(nums);
        int posCount = n - firstPositive; // 正数个数

        return Math.max(negCount, posCount);
    }

    // 查找第一个 >=0 的位置
    private int findFirstNonNegative(int[] nums) {
        int left = 0, right = nums.length - 1;
        int idx = nums.length; // 默认值（全负数情况）
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= 0) {
                idx = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return idx;
    }

    // 查找第一个 >0 的位置
    private int findFirstPositive(int[] nums) {
        int left = 0, right = nums.length - 1;
        int idx = nums.length; // 默认值（无正数情况）
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > 0) {
                idx = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return idx;
    }
}